/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wulangaaa
 * Date: 2025-04-13
 * Time: 14:27
 */
public class RBTree {
    class RBTreeNode{
        public RBTreeNode left;
        public RBTreeNode right;
        public RBTreeNode parent;
        public COLOUR colou=COLOUR.red;
        public int val;

        public RBTreeNode(int val) {
            this.val = val;
        }
    }
    RBTreeNode parent;
    RBTreeNode root;
    //插入数据
    public boolean insert(int val) {
        RBTreeNode node = new RBTreeNode(val);
        RBTreeNode cur=root;
        if (root == null) {
            root =node;
            root.colou=COLOUR.black;
                return true;
        }
        while (cur != null) {
            if (cur.val>val){
                parent=cur;
                cur=cur.left;
            }else if (cur.val<val){
                parent=cur;
                cur=cur.right;
            }else {
                System.out.println("输入的数据已经存在，插入失败");
                return false;
            }
        }
        if (parent.val>val){
            parent.left=node;
        }else {
            parent.right=node;
        }
        node.parent=parent;
        //插入完毕---开始调整颜色和长度--使其成为rb树
        cur=node;

        while (parent!=null&&parent.colou==COLOUR.red) {
            RBTreeNode grandparent=parent.parent;
            //p在grandparent的左边
            if (grandparent.left == parent) {
                RBTreeNode uncle = grandparent.right;
                // 1-- uncle为红的情况
                if (uncle!=null&&uncle.colou == COLOUR.red) {
                    parent.colou = COLOUR.black;
                    uncle.colou = COLOUR.black;
                    grandparent.colou = COLOUR.red;
                    cur=grandparent;
                    parent=cur.parent;
                }else {
                    //2--- uncle不为空或者 存在为黑的-----又分细分为两情况 A B
                    //情况:B-->cur在parent的右边
                    //先将parent左旋---->cur和parent位置互换--->变为情况A
                    if (parent.right==cur){
                        rotateLeft(parent);
                        RBTreeNode tmp=cur;
                        cur=parent;
                        parent=tmp;
                    }

                    //情况：A-->cur在parent的左边
                    rotateRight(grandparent);
                    parent.colou=COLOUR.black;
                    grandparent.colou=COLOUR.red;

                    //uncle为空或者为黑的情况
                }
            }


            else {
                //parent在grandparent的右边
                RBTreeNode uncle = grandparent.left;
                // 1-- uncle为红的情况
                if (uncle!=null&&uncle.colou == COLOUR.red) {
                    parent.colou = COLOUR.black;
                    uncle.colou = COLOUR.black;
                    grandparent.colou = COLOUR.red;
                    cur=grandparent;
                    parent=cur.parent;

                }else {
                    //2--- uncle不为空或者 存在为黑的-----又分细分为两情况 A B
                    //情况:B-->cur在parent的右边
                    //先将parent左旋---->cur和parent位置互换--->变为情况A
                    if (parent.left==cur){
                        rotateRight(parent);
                        RBTreeNode tmp=cur;
                        cur=parent;
                        parent=tmp;
                    }

                    //情况：A-->cur在parent的左边
                    rotateLeft(grandparent);
                    parent.colou=COLOUR.black;
                    grandparent.colou=COLOUR.red;
                    //uncle为空或者为黑的情况
                }
            }
            root.colou=COLOUR.black;
        }
        return true;
    }
    private void rotateLeft(RBTreeNode parent) {
        RBTreeNode subR = parent.right;
        RBTreeNode subRL =subR.left;
        parent.right = subRL;
        subR.left = parent;
        if(subRL != null) {
            subRL.parent = parent;
        }

        RBTreeNode pParent = parent.parent;
        parent.parent = subR;

        if(root == parent) {
            root = subR;
            root.parent = null;
        }else {
            if(pParent.left == parent) {
                pParent.left = subR;
            }else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
    }

    /**
     * 右单旋
     * @param parent
     */
    private void rotateRight(RBTreeNode parent) {

        RBTreeNode subL = parent.left;
        RBTreeNode subLR = subL.right;

        parent.left = subLR;
        subL.right = parent;
        //没有subLR
        if(subLR != null) {
            subLR.parent = parent;
        }
        //必须先记录
        RBTreeNode pParent = parent.parent;
        parent.parent = subL;
        //检查 当前是不是就是根节点
        if(parent == root) {
            root = subL;
            root.parent = null;
        }else {
            //不是根节点，判断这棵子树是左子树还是右子树
            if(pParent.left == parent) {
                pParent.left = subL;
            }else {
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
    }
    //检验红黑树
    public boolean isBRT(RBTreeNode root){
        if (root==null){
            return true;
        }
        //判断是否满足根节点是黑色
        if (root.colou!=COLOUR.black){
            return false;
        }
        int BlackNum=0;
        RBTreeNode cur=root;
        while (cur!=null){
            if (cur.colou==COLOUR.black){
                BlackNum++;
            }
            cur=cur.left;
        }
    return checkBlackNum(root,0,BlackNum)&&chekRed(root);


    }
    //判断是否满足红色节点不能相连 递归实现
    public static boolean chekRed(RBTreeNode root){//root!=null
        if (root==null){
            return true;
        }
        //思路：判断当前节点和他的父亲节点是否都是红色
        if (root.colou==COLOUR.red){
            RBTreeNode parent=root.parent;
            if (parent.colou==COLOUR.red){
                System.out.println("红色节点相连，不是rb树");
                return false;
            }
        }
        return chekRed(root.left) &&chekRed(root.right);

    }
//判断是否满足每条路径上黑色节点数相同；
public static boolean checkBlackNum(RBTreeNode root,int pathNumk,int BlackNum){
    if (root==null){
        return true;
    }
    if (root.colou==COLOUR.black){
        pathNumk++;
    }
    //叶子节点是每条路径的终点
    if (root.left==null&&root.right==null){
        //抵达叶子节点开始判断
        if (pathNumk!=BlackNum){
            System.out.println("路径上黑色节点数不一样");
            return false;
        }
    }
    //递推公式？
    return checkBlackNum(root.left,pathNumk,BlackNum)&&checkBlackNum(root.right,pathNumk,BlackNum);

}



    //中序遍历判断是否是二叉搜索树
    public static void  inorder(RBTreeNode root){
        if (root==null){
        return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);

    }


}
